package org.KeyCrafter.ds.dict;

import java.util.Random;

/**
 * 本类(Dict) 对 DictEntry 和 DictHT 进行了一次封装
 * 其中：
 *  1. DictEntry为哈希表中节点数据(key-value)存储形式， 使用一个对象封装起来
 *  2. DictHT是哈希表的定义
 */
public class HashDict implements Dict{
    private class DictIteratorImpl implements DictIterator{
        // 被迭代器迭代的字典对象
        private HashDict d;
        // 当前迭代到Hash表中哪个索引值
        private int index;
        // table 用于表示当前正在迭代的dict中的Hash表
        private int table;
        // 迭代器是否安全的标识
        private boolean safe;

        // 当前迭代到的节点指针
        private DictEntry entry;

        // 逻辑上的下一个节点
        private DictEntry logicalNext;

        /**
         * 当前迭代到节点的下一个节点的指针(在哈希桶上)
         * 解释：
         *      entry和 nextEntry 两个指针分别指向Hash冲突后的两个父子节点，
         *      如果在安全模式下，删除了 entry节点，nextEntry节点可以保证后续迭代数据不丢失。
         */
        private DictEntry nextEntry;

        // 普通迭代器中用于检测字典结构是否发生变化
        private long fingerprint;

        public DictIteratorImpl() {
            this.d = HashDict.this;
            this.table = 0;
            this.index = -1;
            this.safe = false;
            this.entry = null;
            this.nextEntry = null;
        }

        @Override
        public boolean isSafe() {
            return this.safe;
        }

        // 释放迭代器
        @Override
        public void release() {
            if (!(this.index == -1 && this.table == 0)){
                // 释放安全迭代器，安全迭代器计数器减一
                if (this.safe){
                    this.d.iterators--;
                }else {
                    // 释放不安全迭代器，需要检验指纹变化与否，变化则不释放
                    assert (this.fingerprint == fingerprint());
                }
            }
            // 释放迭代器
            this.d = null;
        }

        @Override
        public boolean hasNext() {
//            // 初次迭代
//            if (this.index == -1 && this.table == 0){
//                return HashDict.this.size() > 0;
//            }
//
//            if (this.nextEntry != null){
//                return true;
//            }else {
//                // 由于超过了我们的索引范围，所以会返回false
//                int curTableSize = HashDict.this.ht[this.table].size;
//                return this.index < curTableSize;
//            }
            throw new UnsupportedOperationException("hasNext");
        }

        /**
         * 返回迭代器指向的当前节点
         * 迭代完毕返回null
         *
         * @return
         */
        @Override
        public Entry next() {
            if (this.d == null){
                throw new RuntimeException("迭代器已失效");
            }
            while (true){

                /**
                 * 进入该循环有两种情况：
                 *      1. 迭代器第一次运行
                 *      2. 当前索引链表中的节点已经迭代完(NULL 为链表结尾)
                 */
                if (this.entry == null){

                    // 指向被迭代的哈希表
                    DictHT ht = this.d.ht[this.table];

                    // 初次迭代时执行
                    if (this.index == -1 && this.table == 0){
                        // 如果是安全迭代器，就更新安全迭代器的计数器
                        if (this.safe){
                            this.d.iterators++;
                        }else {
                            //否则记录指纹
                            this.fingerprint = fingerprint();
                        }
                    }
                    // 更新索引
                    this.index++;

                    // 如果迭代器的当前索引大于当前被迭代的哈希表大小，说明已经迭代完毕
                    if (this.index >= ht.size){
                        // 判断是否在rehash
                        if (isRehashing() && this.table == 0){
                            // 说明此时1表也在使用，需要继续遍历哈希表1
                            this.table++;
                            this.index = 0;
                            ht = this.d.ht[1];
                        }else {
                            // 没有rehash，迭代完成退出循环
                            break;
                        }
                    }
                    // 更新节点指针，指向下一个索引链表的表头节点
                    this.entry = ht.table[this.index];
                }else {
                    // 说明正在迭代过程中，结点指针指向下一个节点
                    this.entry = this.nextEntry;
                }

                // 如果当前节点不为空，那么也记录下该节点的下个节点
                // 因为安全迭代器可能会将迭代器返回的当前节点删除
                if (this.entry != null){
                    this.nextEntry = this.entry.next;
                    return this.entry;
                }
            }
            // 迭代完毕
            return null;
        }
    }

    /**
     * 字典当前状态的哈希值
     * @return
     */
    long fingerprint() {
        long[] integers = new long[6];
        long hash = 0;
        int j;

        integers[0] = this.ht[0].table == null ? 0 : this.ht[0].table.hashCode();
        integers[1] = this.ht[0].size;
        integers[2] = this.ht[0].used;
        integers[3] = this.ht[1].table == null ? 0 : this.ht[0].table.hashCode();
        integers[4] = this.ht[1].size;
        integers[5] = this.ht[1].used;

        for (j = 0; j < 6; j++) {
            hash += integers[j];
            hash = (~hash) + (hash << 21); // hash = (hash << 21) - hash - 1;
            hash = hash ^ (hash >> 24);
            hash = (hash + (hash << 3)) + (hash << 8); // hash * 265
            hash = hash ^ (hash >> 14);
            hash = (hash + (hash << 2)) + (hash << 4); // hash * 21
            hash = hash ^ (hash >> 28);
            hash = hash + (hash << 31);
        }
        return hash;
    }


    // 静态类定义节点属性
    private static class DictEntry implements Dict.Entry {
        // 键
        Object key;
        // 值
        Object value;
        // 指向下个哈希表节点，形成链表
        DictEntry next;

        @Override
        public Object getKey() {
            return key;
        }

        @Override
        public Object getValue() {
            return value;
        }

        @Override
        public void setValue(Object value) {
            this.value = value;
        }
    }

    // 定义哈希表
    private static class DictHT{
        /*
        1. 指针数组用于存放键值对
        2. 该数组中元素指向dictEntry
         */
        DictEntry[] table;
        // table大小
        int size;
        /*
        1. 用来计算建的索引值
        2. sizemask值恒等于 size - 1
         */
        int sizeMask;
        // table数组已存元素，包含next单链表的数据
        int used;
    }

    // 该字典特定的操作函数
    DictType type;
    // 该字典依赖的数据
    Object privdata;
    // 哈希表
    DictHT[] ht;
    // 随机数生成
    private static final Random random = new Random();
    /*
    1. rehash 标识，代表没有进行rehash操作，值为 -1。
    2. 若在进行rehash操作，存储值代表哈希表ht[0] 的rehash操作进行到了哪个索引值。
     */
    int rehashidx;
    
    /*
    1. 目前正在运行安全迭代器数量
    2. 说明：
        当有安全迭代器绑定到该字典时，会暂停rehash操作。
     */
    int iterators;


    // 初始化一个空字典
    public HashDict(DictType type, Object privdata){
        this.ht = new DictHT[2];
        ht[0] = new DictHT();
        ht[1] = new DictHT();
        dictInit(type, privdata);
    }

    // 重置给定hash表各项属性
    private void  dictReset(DictHT ht){
        ht.table = null;
        ht.size = 0;
        ht.sizeMask = 0;
        ht.used = 0;
    }

    private int dictInit(DictType type, Object privdata) {
        //初始化两个哈希表属性
        /*
        为什么创建两个表？
        答：在rehash过程中，若表ht【0】在rehash，那么数据就存放在ht【1】中,
        完成rehash后将表1设置为新的表1，将重置后的表0设置为新的表1
         */
        dictReset(this.ht[0]);
        dictReset(this.ht[1]);

        // 设置类型特定函数
        this.type = type;
        // 设置私有数据
        this.privdata = privdata;

        // 设置哈希表 rehash 状态
        this.rehashidx = -1;

        // 设置字典的安全迭代器数量
        this.iterators = 0;

        return DICT_OK;
    }

    @Override
    public int add(Object key, Object value) {
        DictEntry entry = addRaw(key);

        // 键已经存在，添加失败
        if(entry == null) return DICT_ERR;

        // 键不存在，设置节点的值
        setVal(entry, value);
        return DICT_OK;
    }

    /**
     *  将键值对添加到dict中，存在以下情况
     *
     *  1: 该键值为新键值
     *  0: 该键值覆盖旧键值
     * @param key
     * @param value
     * @return
     */
    @Override
    public int replace(Object key, Object value) {
        DictEntry entry, auxentry;

        // 尝试直接将键值对添加到字典
        // 如果键 key 不存在的话，添加成功
        if (add(key, value) == DICT_OK) return 1;

        entry = find(key);
        // 先保存原有的值的指针
        auxentry = entry;
        // 设置覆盖新值
        setVal(entry, value);
        // 释放旧值
        freeValue(auxentry);
        return 0;
    }

    /**
     * 根据给定key存在与否，执行以下操作：
     *      1. key存在，返回包含该 key 的字典节点
     *      2. key不存在，那么将 key 添加到字典
     *
     * 不论执行哪种操作，总返回包含给定 key 的字典节点
     * @param key
     * @return
     */
    @Override
    public Entry replaceRaw(Object key) {
        DictEntry entry = this.find(key);
        // 返回
        return entry != null ? entry : addRaw(key);
    }

    @Override
    public Object fetchValue(Object key) {
        DictEntry he;
        he = find(key);
        return he != null ? he.value : null;
    }

    @Override
    public int delete(Object key) {
        return genericDelete(key, true);
    }

    /**
     * 返回字典中包含key的节点
     * @param key
     * @return
     */
    public DictEntry find( final Object key){
        DictEntry he;
        int h, idx, table;

        //字典的哈希表为空
        if (this.ht[0].size == 0){
            return null;
        }
        // 如果条件允许的话，进行单步 rehash
        if (isRehashing()) rehashStep();

        // 计算键的哈希值
        h = hashKey(key);

        // 在字典的哈希表中查找这个键
        for (table = 0; table <= 1; table++){
            // 计算索引值
            idx = h & this.ht[table].sizeMask;

            // 遍历给定索引上所有节点，查找 key
            he = this.ht[table].table[idx];
            while(he != null){
                if (compareKeys(key, he.key)){
                    return he;
                }
                he = he.next;
            }
            // 判断是否在进行 rehash
            // 如果否则返回NULL
            // 如果是则继续查找 1 号哈希表
            if (!isRehashing()){
                return null;
            }
        }
        return null;
    }

    int genericDelete(Object key, boolean nofree) {
        int h, idx;
        DictEntry he, prevHe;
        int table;

        // 字典的哈希值为空
        if (this.ht[0].size == 0){
            return DICT_ERR;
        }

        // 进行单步rehash
        if (isRehashing()){
            rehashStep();
        }
        // 计算哈希值
        h = hashKey(key);

        // 遍历哈希表
        // T = O(1)
        for (table = 0; table <= 1; table++) {
            // 计算索引值
            idx = h & this.ht[table].sizeMask;
            // 指向该索引上的链表
            he = this.ht[table].table[idx];
            prevHe = null;
            while (he != null){
                if (compareKeys(key, he.key)){
                    // 查询目标节点
                    // 从链表中删除
                    if (prevHe != null){
                        prevHe.next = he.next;
                    }else {
                        this.ht[table].table[idx] = he.next;
                    }

                    // 释放调用键和值的释放函数
                    if (!nofree){
                        freeKey(he);
                        freeValue(he);
                    }
                    // 更新已经使用节点
                    this.ht[table].used--;
                    return DICT_OK;
                }
                prevHe = he;
                he = he.next;
            }
            if (!isRehashing()) break;
        }
        return DICT_ERR;
    }

    // 释放字典指定的键
    void freeKey(DictEntry entry) {
        this.type.keyDestructor(this.privdata, entry.key);
    }

    // 释放字典指定的值
    void freeValue(DictEntry entry) {
        this.type.valDestructor(this.privdata, entry.value);
    }

    @Override
    public void empty() {
        clear(this.ht[0]);
        clear(this.ht[1]);
        this.rehashidx = -1;
        this.iterators = 0;
    }

    /**
     * 随机返回字典中任意一个节点
     * 如果为空返回null
     * @return
     */
    @Override
    public Entry getRandomKey() {
        DictEntry he = null, origHe = null;
        int h;
        int listlen, listele;

        // 校验字典是否为空
        if (this.size() == 0){
            return null;
        }

        // 进行单步rehash
        if (this.isRehashing()){
            this.rehashStep();
        }

        // 如果在rehash则将表1也纳入随机范围
        if (this.isRehashing()){
            do {
                h = getIntRandom() % (this.ht[0].size + this.ht[1].size);
                he = (h >= this.ht[0].size) ? this.ht[1].table[h - this.ht[0].size] :
                        this.ht[0].table[h];
            }while (he == null);
        }else {
            do {
                h = getIntRandom() & this.ht[0].sizeMask;
                he = this.ht[0].table[h];
            } while (he == null);
        }
        // he已经指向一个非空链表
        // 从该链表随机取一个点
        listlen = 0;
        origHe = he;
        // 计算节点数量
        while (he != null){
            he = he.next;
            listlen++;
        }
        // 取模，得出随机节点的索引
        listele = getIntRandom() % listlen;
        he = origHe;

        // 按照索引查找节点
        while (listele-- > 0){
            he = he.next;
        }
        return he;
    }

    /**
     * 字典缩容
     * 缩容条件：已经使用节点和字典大小之间的比率接近 1:1
     * 返回 DICT_ERR 表示字典已经在 rehash ，或者 dict_can_resize 为假。
     * 成功创建体积更小的 ht[1] ，可以开始 resize 时，返回 DICT_OK。
     * @return
     */
    @Override
    public int resize() {
        int minimal;
        // 不能在未启用rehash或者正在rehash时调用
        if (!dict_can_resize || this.isRehashing()){
            return DICT_ERR;
        }

        // 计算比率解决 1：1 所需最少节点
        minimal = this.ht[0].used;
        if (minimal < DICT_HT_INITIAL_SIZE){
            minimal = DICT_HT_INITIAL_SIZE;
        }
        return expand(minimal);
    }

    private int getIntRandom() {
        int r = random.nextInt();
        return r >= 0 ? r : -r;
    }

    private int clear(DictHT ht){
        dictReset(ht);
        return DICT_OK;
    }

    @Override
    public long slots() {
        return this.ht[0].size + this.ht[1].size;
    }

    @Override
    public DictIterator getIterator() {
        return this.new DictIteratorImpl();
    }

    @Override
    public DictIterator getSafeIterator() {
        DictIteratorImpl iter = this.new DictIteratorImpl();
        iter.safe = true;
        return iter;

    }

    @Override
    public long size() {
        return this.ht[0].used + this.ht[1].used;
    }

    /**
     * 主要作用为添加或查找键，添加成功就返回新节点，查找成功返回 NULL 并把老节点存入existing 字段
     * 核心是调用 keyIndex函数
     * @param key
     * @return
     */
    private DictEntry addRaw(Object key){
        int index;
        DictEntry entry;
        DictHT ht;

        // 条件允许进行rehash
        if (isRehashing()){
            rehashStep();
        }

        // 计算键在hash表中的索引值
        // 如果为 -1 则标识键已经存在
        if((index = keyIndex(key)) == -1) return null;

        // 如果字典正在rehash， 那么新键添加到 1 号哈希表
        //否则添加到 0 号哈希表。
        ht = isRehashing() ? this.ht[1] : this.ht[0];

        // 为新的键分配新的节点空间
        entry = new DictEntry();
        // 将新的节点插入到链表表头
        entry.next = ht.table[index];
        ht.table[index] = entry;
        // 更新哈希表已使用节点数量
        ht.used++;

        // 设置新节点的键
        setKey(entry, key);
        return entry;
    }

    // 设置给定字典节点的键
    void setKey(DictEntry entry, Object key) {
        entry.key = this.type.keyDup(this.privdata, key);
    }

    // 设置给定字典节点的值
    void setVal(DictEntry entry, Object value) {
        entry.value = this.type.valDup(this.privdata, value);
    }

    /**
     * 返回可以将 key 插入到哈希表索引位置
     * 如果key存在于哈希表，返回 -1
     * 作用:
     *  获取键的索引值
     * @param key
     * @return
     */
    private int keyIndex(Object key) {
        int h, idx = 0, table;
        DictEntry he;

        // 单步rehash
        if (expandIfNeeded() == DICT_ERR) return -1;

        // 计算 key 的哈希值
        h = hashKey(key);
        for (table = 0; table <= 1; table++){
            //计算索引值
            idx = h & this.ht[table].sizeMask;

            //查找 key 是否存在
            he = this.ht[table].table[idx];
            while (he != null){
                if (compareKeys(key, he.key)){
                    return -1;
                }
                he = he.next;
            }

            // 此时说明 0 号表所有节点都不包含要加入的key
            // 继续rehash
            if (!isRehashing()) break;
        }
        return idx;
    }

    private int expandIfNeeded() {
        // 如果渐进式rehash已经在进行了，就直接返回
        if (isRehashing()) return DICT_OK;

        // 如果字典的0号哈希表为空，那么创建并返回初始化小的 0号哈希表
        if (this.ht[0].size == 0){
            return expand(DICT_HT_INITIAL_SIZE);
        }

        /**
         * 以下两个条件有一个为真时，对字典进行扩容
         * 1. 字典已使用节点数和字典大小之比接近 1 : 1，并且 dict_can_resize 为真
         * 2. 已使用节点数和字典大小之间的比率超过 dict_force_resize_ratio
         */
        if (this.ht[0].used >= this.ht[0].size &&
                (dict_can_resize
                        || this.ht[0].used/ this.ht[0].size > dict_force_resize_ratio)){
            // 根据扩容机制，新的hash表大小为目前已使用节点数的两倍
            return expand(this.ht[0].used * 2);
        }

        return DICT_OK;
    }

    /**
     * 扩容主要流程:
     *  1. 申请一个内存初次申请默认容量为 4 个dictEntry
     *      非初次申请大小为当前Hash表容量的一倍
     *  2. 把新申请的内存地址赋值给ht【1】 并且把字典的rehashidx标识由-1 改为 0，标识之后需要进行rehash操作
     * @param size
     * @return
     */
    int expand(int size) {
        // 新建hash表
        DictHT n = new DictHT();

        // 根据size参数计算哈希表大小
        // 真实分配内存空间大小
        int realsize = nextPower(size);

        // 正在rehash不能扩容
        // size小于0号数组已使用节点，不能扩容
        if (isRehashing() || this.ht[0].used > size){
            return DICT_ERR;
        }

        // 为哈希表分配空间，将所有的指针指向NULL
        n.size = realsize;
        n.sizeMask = realsize - 1;
        n.table = new DictEntry[realsize];
        n.used = 0;

        // 如果 0 号哈希表为空，那么这是一次初始化：
        // 程序将新哈希表赋给 0 号哈希表的指针，然后字典就可以开始处理键值对了。
        if (this.ht[0].table == null) {
            this.ht[0] = n;
        } else {
            // 如果 0 号哈希表非空，那么这是一次 rehash ：
            // 程序将新哈希表设置为 1 号哈希表，
            // 并将字典的 rehash 标识打开，让程序可以开始对字典进行 rehash
            this.ht[1] = n;
            this.rehashidx = 0;
        }
        return DICT_OK;
    }

    /**
     * 重新计算扩容后的值，必须为 2的 N 次方幂
     * @param size
     * @return
     */
    private int nextPower(long size){
        int i = DICT_HT_INITIAL_SIZE;
        if (i > Integer.MAX_VALUE){
            return Integer.MAX_VALUE;
        }
        while (true){
            if (i >= size)
                return i;
            i *= 2;
        }
    }

    // 比较两个键
    boolean compareKeys(Object key1, Object key2){
        return this.type.keyCompare(this.privdata, key1, key2);
    }
    // 计算哈希值
    int hashKey(Object key) {
        return this.type.hashFunction(key);
    }

    /*
     * 在给定毫秒数内，以 100 步为单位，对字典进行 rehash 。
     *
     * T = O(N)
     */
    @Override
    public int rehashMilliseconds(int ms) {
        // 记录开始时间
        long start = System.currentTimeMillis();
        int rehashes = 0;

        while(this.rehash(100)!=0) {
            rehashes += 100;
            // 如果时间已过，跳出
            if (System.currentTimeMillis()-start > ms){
                break;
            }
        }
        return rehashes;
    }

    /**
     * 在字典不存在安全迭代器情况下，进行单步rehash。
     * 字典具有安全迭代器情况下停止rehash操作
     * 两种迭代可能会让字典存储混乱
     *
     * 这个函数可以被多个通用查查找、更新操作调用
     * 让字典在被使用同时进行rehash
     */
    private void rehashStep() {
        if (this.iterators == 0){
            rehash(1);
        }
    }

    /**
     * 执行 n 步 渐进式 rehash。
     *
     * 返回 1 表示仍有键需要从 0 号hash表移动到 1 号hash表
     * 返回 0 表示所有键都已经完成迁移
     *
     * 注意：
     *  每部rehash都是以一个hash桶为单位，
     *  即将当前节点链表为一个rehash单位(存在多个节点)
     *  所有被rehash 的 hash桶 都会被移动到新的哈希表
     *
     * @param n
     * @return
     */
    int rehash(int n) {
        // 只可以在 rehash进行中时执行
        if (!isRehashing()){
            return 0;
        }

        // N步rehash
        while(n-- > 0){
            DictEntry de, nextde;
            // 如果 0 号hash表为空，那么表示rehash执行完毕
            if (this.ht[0].used == 0){
                // 释放 0 号哈希表
                this.ht[0].table = null;
                // 将原来的 1 号哈希表重置为新的 0 号哈希表
                this.ht[0] = this.ht[1];
                // 重置旧的1号哈希表
                this.ht[1] = new DictHT();
                dictReset(this.ht[1]);
                //关闭rehash标识
                this.rehashidx = -1;
                return 0;
            }

            /**
             * 1. 确保 rehashidx 没有越界
             * 2. 解释:
             *      由于前文说了，如果在rehashing中，rehashidx存储的是当前正在rehash索引位置
             *      ，显然该位置应该小于我们的table数组大小。
             */
            assert this.ht[0].size > this.rehashidx;
            /**
             * 1. 忽略为空索引
             * 2. 解释:
             *      同理，和上个方法一样，此处获取rehasing位置,初始位置为头节点
             *      ，如果为null表示为空索引，我们要找到下一个非空索引。
             */
            while (this.ht[0].table[this.rehashidx] == null){
                this.rehashidx++;
            }
            // 指向该索引的链表表头节点
            de = this.ht[0].table[this.rehashidx];
            // 将链表所有数据迁移到新的哈希表
            while (de != null){
                int h;
                // 保存下个节点指针
                nextde = de.next;

                // 计算新哈希表的哈希值，以及节点插入的索引位置(类似keyIndex)
                h = hashKey(de.key) & this.ht[1].sizeMask;

                // 插入节点到新哈希表
                de.next = this.ht[1].table[h];
                this.ht[1].table[h] = de;

                // 更新计数器
                this.ht[0].used--;
                this.ht[1].used++;

                //继续处理下个节点
                de = nextde;
            }

            // 将0 表的索引指针设为空
            this.ht[0].table[this.rehashidx] = null;
            // 更新 rehash 索引
            this.rehashidx++;
        }
        return 1;
    }

    // 查看字典是否正在 rehash
    public boolean isRehashing() {
        return this.rehashidx != -1;
    }
}
